#include <iostream>
#include <queue>
#include <climits>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1
using namespace std;
struct Node{
int value;
Node* next=nullptr;
Node(int _value): value(_value) {}
};
struct Vertex{
int color=WHITE, d=INT_MAX, pi=NIL;
Vertex(){}
};
struct adjList{
Node** aL;
Vertex* vertex;
int vN, eN;
adjList(int _vN, int E[][2], int _eN): vN(_vN), eN(_eN){
vertex=new Vertex[this->vN];
aL=new Node*[this->vN];
for(int i=0; i<this->eN; ++i){
Node* nN1=new Node(E[i][1]);
Node* nN2=new Node(E[i][0]);
if(aL[E[i][0]-1]==nullptr){
aL[E[i][0]-1]=nN1;
} else {
Node* tmp=aL[E[i][0]-1];
aL[E[i][0]-1]=nN1;
nN1->next=tmp;
}
if(aL[E[i][1]-1]==nullptr){
aL[E[i][1]-1]=nN2;
} else {
Node* tmp=aL[E[i][1]-1];
aL[E[i][1]-1]=nN2;
nN2->next=tmp;
}
}
}
void BFS(int s){
for(int i=0; i<this->vN; ++i){
this->vertex[i].color=WHITE;
this->vertex[i].d=INT_MAX;
this->vertex[i].pi=NIL;
}
vertex[s-1].color=GRAY;
vertex[s-1].d=0;
vertex[s-1].pi=NIL;
std::queue<int> Queue;
Queue.push(s);
while(!Queue.empty()){
int u=Queue.front();
Queue.pop();
Node* cur=this->aL[u-1];
while(cur!=nullptr){
int v=cur->value;
if(this->vertex[v-1].color==WHITE){
vertex[v-1].color=GRAY;
vertex[v-1].d=vertex[u-1].d+1;
vertex[v-1].pi=u;
Queue.push(v);
}
cur=cur->next;
}
vertex[u-1].color=BLACK;
}
}
void printPath(int s, int v){
if(v==s) std::cout<<s<<' ';
else if(this->vertex[v-1].pi==NIL){
std::cout<<"NO PATH FROM "<<s<<" TO "<<v<<std::endl;
} else {
this->printPath(s, this->vertex[v-1].pi);
std::cout<<v<<' ';
}
}
};
int main(void){
int E[][2]={
{1, 2},
{2, 3},
{3, 4},
{4, 5},
{4, 6},
{5, 6},
{6, 7},
{5, 7},
{5, 8},
{7, 8}
};
adjList* graph=new adjList(8, E, 10);
graph->BFS(3);
graph->printPath(3, 8);
return 0;
}